package com.basic.dp;

/**
 * DPBackPack..
 *
 * dp[i][v]=max(dp[i−1][v],dp[i−1][v−c[i]]+w[i]）
 * ，一步步，求出最大值
 *
 * @author Lizhong
 * @date 2019/10/11
 */
public class DPBackPack {
    static int[] w = {0, 35, 30, 60, 50, 40, 10, 25};
    static int[] p = {0, 10, 40, 30, 50, 35, 40, 30};

    /**
     * 从小到大
     * @param mW
     */
    public static void method01(int mW) {
        int[][] dp = new int[p.length][mW + 1];
        for (int i = 1; i < w.length; i++) {
            for (int j = 0; j <= mW; j++) {
                if (j < w[i])
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + p[i]);
            }

        }
        System.out.println(dp[p.length - 1][mW]);

    }

    /**
     * 从大到小
     * @param mW
     */
    public static void method02(int mW) {
        int[][] dp = new int[p.length][mW + 1];
        for (int i = 1; i < w.length; i++) {
            for (int j = mW; j >= 0; j--) {
                if (j < w[i])
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + p[i]);
            }
        }
        System.out.println(dp[p.length - 1][mW]);

    }

    /**
     * 优化成当行数组
     * @param mW
     */
    public static void method03(int mW) {
        int[] dp = new int[200];
        for (int i = 1; i < w.length; i++) {
            for (int j = mW; j >= w[i]; j--)
                dp[j] = max(dp[j], dp[j - w[i]] + p[i]);
        }

        System.out.println(dp[mW]);

    }


    static public int max(int i, int j) {
        return i > j ? i : j;
    }

    public static void main(String[] args) {
        method03(150);
    }
}
